/**
 * @brief 二叉树的模板类实现
 * @author TMJ
 * @date 2023-12-24
 * @version 1.0
 */

#ifndef TREE_BINARY_TREE_H
#define TREE_BINARY_TREE_H

#include <iostream>
#include <stack>
#include <queue>

// 二叉树结点的定义
template<typename type>
struct BinaryTreeNode {
    BinaryTreeNode() : lChild(lChild), rChild(rChild) {}

    explicit BinaryTreeNode(const type &data, BinaryTreeNode<type> *rChild = nullptr,
                            BinaryTreeNode<type> *lChild = nullptr)
            : data(data), lChild(lChild), rChild(rChild) {}

    type data;                   // 数据域
    BinaryTreeNode<type> *lChild;// 左指针
    BinaryTreeNode<type> *rChild;// 右指针
};

// 二叉树结构定义
template<typename type>
class BinaryTree {
public:
    // 构造函数
    BinaryTree() : _root(nullptr) {}

    // 指定根节点数据的构造函数
    explicit BinaryTree(const type &data) { _insertInSubTreeRecursive(this->_root, data); }

    // 拷贝构造函数
    BinaryTree(BinaryTree<type> &srcTree);

    // 析构函数
    ~BinaryTree() { _deleteInSubTreeRecursive(this->_root); }

    // 判断是否为空树
    bool isEmpty() const { return this->_root == nullptr; }

    // 获取父节点
    BinaryTreeNode<type> *getParent(BinaryTreeNode<type> *node) const {
        return (this->_root == nullptr || this->_root == node) ?
               nullptr : _getParentInSubTree(this->_root, node);
    }

    // 获取根节点
    BinaryTreeNode<type> *getRoot() const { return this->_root; }

    // 获取树的高度
    int getHeight() { return _getHeightOfSubTree(this->_root); }

    // 获取节点数
    int getSize() { return _getSizeOfSubTree(this->_root); }

    // 插入结点(递归)
    bool insertDataByRecursive(const type &data) { return _insertInSubTreeRecursive(this->_root, data); }

    // 检测是否存在数据
    bool isExist(const type &data) { return _isExistInSubTree(this->_root, data); }

    // 前序遍历（递归）
    void preorderTraversalRecursive(void (*visit)(BinaryTreeNode<type> *)) {
        _preorderSubTreeByRecursive(this->_root, visit);
    }

    // 前序遍历（非递归）
    void preorderTraversal(void (*visit)(BinaryTreeNode<type> *)) {
        _preorderSubTree(this->_root, visit);
    }

    // 中序遍历（递归）
    void inorderTraversalRecursive(void (*visit)(BinaryTreeNode<type> *)) {
        _inorderSubTreeByRecursive(this->_root, visit);
    }

    // 中序遍历（非递归）
    void inorderTraversal(void (*visit)(BinaryTreeNode<type> *)) {
        _inorderSubTree(this->_root, visit);
    }

    // 后序遍历递归
    void postorderTraversalRecursive(void (*visit)(BinaryTreeNode<type> *)) {
        _postorderSubTreeByRecursive(this->_root, visit);
    }

    // 层序遍历
    void levelOrderTraversal(void (*visit)(BinaryTreeNode<type> *)) { _levelSubTree(this->_root, visit); }

    // 通过前序遍历和中序遍历序列创建二叉树
    bool createSubTreeByPreorderAndInOrder(type *preList, type *inList, int length) {
        return _createSubTreeByPreorderAndInOrder(preList, inList, length, this->_root);
    }

    // 打印二叉树
    void print() const { _printSubTree(this->_root); }

    // 判断两棵二叉树是否相同
    static bool equal(BinaryTreeNode<type> *root_1, BinaryTreeNode<type> *root_2);

protected:
    // 子树插入结点
    bool _insertInSubTreeRecursive(BinaryTreeNode<type> *&subRoot, const type &data);

    // 子树删除结点
    void _deleteInSubTreeRecursive(BinaryTreeNode<type> *&subRoot);

    // 判断子树是否存在数据
    bool _isExistInSubTree(BinaryTreeNode<type> *subRoot, const type &data) const;

    // 拷贝树
    bool _copySubTreeRecursive(BinaryTreeNode<type> *srcRoot, BinaryTreeNode<type> *&targetRoot);

    // 求子树高度
    int _getHeightOfSubTree(BinaryTreeNode<type> *srcRoot) const;

    // 求子树结点个数
    int _getSizeOfSubTree(BinaryTreeNode<type> *srcRoot) const;

    // 子树获取结点的父节点
    BinaryTreeNode<type> *_getParentInSubTree(BinaryTreeNode<type> *subRoot, BinaryTreeNode<type> *srcNode) const;

    // 子树前序遍历（递归）
    void _preorderSubTreeByRecursive(BinaryTreeNode<type> *subRoot, void (*visit)(BinaryTreeNode<type> *));

    // 子树前序遍历（非递归）
    void _preorderSubTree(BinaryTreeNode<type> *subRoot, void (*visit)(BinaryTreeNode<type> *));

    // 子树中序遍历（递归）
    void _inorderSubTreeByRecursive(BinaryTreeNode<type> *subRoot, void (*visit)(BinaryTreeNode<type> *));

    // 子树中序遍历（非递归）
    void _inorderSubTree(BinaryTreeNode<type> *subRoot, void (*visit)(BinaryTreeNode<type> *));

    // 子树后序遍历（递归）
    void _postorderSubTreeByRecursive(BinaryTreeNode<type> *subRoot, void (*visit)(BinaryTreeNode<type> *));

    // 子树层序遍历
    void _levelSubTree(BinaryTreeNode<type> *subRoot, void (*visit)(BinaryTreeNode<type> *));

    // 子树打印
    void _printSubTree(BinaryTreeNode<type> *subRoot) const ;

    // 通过前序和中序遍历创建子树
    bool _createSubTreeByPreorderAndInOrder(type *preorderList, type *inorderList, int length,
                                            BinaryTreeNode<type> *&subRoot);

    BinaryTreeNode<type> *_root;// 根节点
};

//拷贝构造函数
template<typename type>
BinaryTree<type>::BinaryTree(BinaryTree<type> &srcTree) {
    bool res = _copySubTreeRecursive(srcTree.getRoot(), this->_root);
    if (!res) { throw std::logic_error("拷贝构造函数出错!"); }
}

// 判断两个二叉树是否相同
template<typename type>
bool BinaryTree<type>::equal(BinaryTreeNode<type> *root_1, BinaryTreeNode<type> *root_2) {
    // 两棵树都是空树
    if (root_1 == nullptr && root_2 == nullptr) { return true; }

    if (root_1 != nullptr && root_2 != nullptr && root_1->data == root_2->data &&
        equal(root_1->lChild, root_2->lChild) && equal(root_1->rChild, root_1->rChild)) {
        return true;
    }

    return false;
}

// 在子树中插入结点
template<typename type>
bool BinaryTree<type>::_insertInSubTreeRecursive(BinaryTreeNode<type> *&subRoot, const type &data) {
    // 空子树处理
    if (subRoot == nullptr) {
        subRoot = new BinaryTreeNode<type>(data);
        if (!subRoot) { return false; }
        return true;
    }

    // 分治递归
    int leftHeight = _getHeightOfSubTree(subRoot->lChild);
    int rightHeight = _getHeightOfSubTree(subRoot->rChild);

    if (leftHeight <= rightHeight) {
        return _insertInSubTreeRecursive(subRoot->lChild, data);
    } else {
        return _insertInSubTreeRecursive(subRoot->rChild, data);
    }
}

// 子树删除
template<typename type>
void BinaryTree<type>::_deleteInSubTreeRecursive(BinaryTreeNode<type> *&subRoot) {
    // 空树处理
    if (subRoot == nullptr) { return; }

    _deleteInSubTreeRecursive(subRoot->lChild);
    _deleteInSubTreeRecursive(subRoot->rChild);

    delete subRoot;
    subRoot = nullptr;
}

// 判断子树是否存在数据
template<typename type>
bool BinaryTree<type>::_isExistInSubTree(BinaryTreeNode<type> *subRoot, const type &data) const {
    // 空树处理
    if (subRoot == nullptr) { return false; }

    // 存在条件处理
    if (subRoot->data == data) { return true; }

    // 子树处理
    if (_isExistInSubTree(subRoot->rChild, data) ||
        _isExistInSubTree(subRoot->lChild, data)) {
        return true;
    }

    return false;
}

// 拷贝子树
template<typename type>
bool BinaryTree<type>::_copySubTreeRecursive(BinaryTreeNode<type> *srcRoot, BinaryTreeNode<type> *&targetRoot) {
    // 空源子树处理
    if (srcRoot == nullptr) {
        targetRoot = nullptr;
        return true;
    }

    // 根节点处理
    targetRoot = new BinaryTreeNode<type>(srcRoot->data);
    if (!targetRoot) { return false; }

    // 分治处理左右子树
    bool res = _copySubTreeRecursive(srcRoot->lChild, targetRoot->lChild);
    if (!res) { return false; }

    res = _copySubTreeRecursive(srcRoot->rChild, targetRoot->rChild);
    if (!res) { return false; }

    return true;
}

// 求子树高度
template<typename type>
int BinaryTree<type>::_getHeightOfSubTree(BinaryTreeNode<type> *srcRoot) const {
    // 空树处理
    if (srcRoot == nullptr) { return 0; }

    // 分治计算左右子树高度
    int rightHeight = _getHeightOfSubTree(srcRoot->rChild);
    int leftHeight = _getHeightOfSubTree(srcRoot->lChild);

    return (rightHeight > leftHeight ? rightHeight : leftHeight) + 1;
}

// 求二叉树结点个数
template<typename type>
int BinaryTree<type>::_getSizeOfSubTree(BinaryTreeNode<type> *srcRoot) const {
    // 空树处理
    if (srcRoot == nullptr) { return 0; }

    int rightSize = _getSizeOfSubTree(srcRoot->rChild);
    int leftSize = _getSizeOfSubTree(srcRoot->lChild);

    return rightSize + leftSize + 1;
}

// 在子树中获取父节点
template<typename type>
BinaryTreeNode<type> *BinaryTree<type>::_getParentInSubTree(BinaryTreeNode<type> *subRoot,
                                                            BinaryTreeNode<type> *srcNode) const {
    // 空树处理
    if (subRoot == nullptr) { return nullptr; }

    // 找到父节点
    if (subRoot->rChild == srcNode || subRoot->lChild == srcNode) { return subRoot; }

    // 分治处理
    auto *parent = _getParentInSubTree(subRoot->lChild, srcNode);
    if (!parent) { parent = _getParentInSubTree(subRoot->rChild, srcNode); }

    return parent;
}

// 子树前序遍历（递归）
template<typename type>
void BinaryTree<type>::_preorderSubTreeByRecursive(BinaryTreeNode<type> *subRoot,
                                                   void (*visit)(BinaryTreeNode<type> *)) {
    if (subRoot == nullptr) {
        return;
    }

    visit(subRoot);

    _preorderSubTreeByRecursive(subRoot->lChild, visit);
    _preorderSubTreeByRecursive(subRoot->rChild, visit);
}

// 子树前序遍历（非递归）
template<typename type>
void BinaryTree<type>::_preorderSubTree(BinaryTreeNode<type> *subRoot, void (*visit)(BinaryTreeNode<type> *)) {
    // 空树处理
    if (subRoot == nullptr) {
        return;
    }

    std::stack<BinaryTreeNode<type> *> backStack;
    backStack.push(subRoot);

    while (!backStack.empty()) {
        auto *cur = backStack.top();
        backStack.pop();

        visit(cur);

        if (cur->rChild) {
            backStack.push(cur->rChild);
        }

        if (cur->lChild) {
            backStack.push(cur->lChild);
        }
    }
}

// 子树中序遍历（递归）
template<typename type>
void BinaryTree<type>::_inorderSubTreeByRecursive(BinaryTreeNode<type> *subRoot,
                                                  void (*visit)(BinaryTreeNode<type> *)) {
    if (subRoot == nullptr) {
        return;
    }

    _inorderSubTreeByRecursive(subRoot->lChild, visit);
    visit(subRoot);
    _inorderSubTreeByRecursive(subRoot->rChild, visit);
}

// 子树中序遍历（非递归）
template<typename type>
void BinaryTree<type>::_inorderSubTree(BinaryTreeNode<type> *subRoot, void (*visit)(BinaryTreeNode<type> *)) {
    // 空树处理
    if (subRoot == nullptr) {
        return;
    }

    std::stack<BinaryTreeNode<type> *> backStack;
    auto *cur = subRoot;

    while (cur != nullptr || !backStack.empty()) {
        // 一直向左子树搜索
        while (cur != nullptr) {
            backStack.push(cur);
            cur = cur->lChild;
        }

        if (!backStack.empty()) {
            cur = backStack.top();
            backStack.pop();

            visit(cur);

            cur = cur->rChild;
        }
    }
}

// 子树后序遍历（递归）
template<typename type>
void BinaryTree<type>::_postorderSubTreeByRecursive(BinaryTreeNode<type> *subRoot,
                                                    void (*visit)(BinaryTreeNode<type> *)) {
    if (subRoot == nullptr) { return; }

    _postorderSubTreeByRecursive(subRoot->lChild, visit);
    _postorderSubTreeByRecursive(subRoot->rChild, visit);
    visit(subRoot);
}

// 子树层序遍历
template<typename type>
void BinaryTree<type>::_levelSubTree(BinaryTreeNode<type> *subRoot, void (*visit)(BinaryTreeNode<type> *)) {
    if (subRoot == nullptr) {
        return;
    }

    std::queue<BinaryTreeNode<type> *> levelQueue;
    levelQueue.push(subRoot);

    while (!levelQueue.empty()) {
        auto *cur = levelQueue.front();
        levelQueue.pop();

        visit(cur);

        if (cur->lChild) {
            levelQueue.push(cur->lChild);
        }

        if (cur->rChild) {
            levelQueue.push(cur->rChild);
        }
    }
}

// 打印子树
template<typename type>
void BinaryTree<type>::_printSubTree(BinaryTreeNode<type> *subRoot) const {
    // ---------- 1 空子树处理 ----------

    if (subRoot == nullptr) {
        return;
    }

    // ---------- 2 打印子树根结点 ----------

    std::cout << subRoot->data;

    // ---------- 3 递归处理左右子树 ----------

    if (subRoot->lChild != nullptr || subRoot->rChild != nullptr) {
        std::cout << '(';
        this->_printSubTree(subRoot->lChild);
        std::cout << ',';
        this->_printSubTree(subRoot->rChild);
        std::cout << ')';
    }
}

// 根据先序序列和中序序列创建二叉树
template<typename type>
bool BinaryTree<type>::_createSubTreeByPreorderAndInOrder(type *preorderList,
                                                          type *inorderList,
                                                          int length,
                                                          BinaryTreeNode<type> *&subRoot) {
    // 空序列处理
    if (length == 0) {
        subRoot = nullptr;
        return true;
    }

    // 中序序列找到轴
    int inorderListPivot = 0;
    type inorderListPivotData = *preorderList;
    while (inorderListPivotData != inorderList[inorderListPivot]) {
        inorderListPivot++;
    }

    subRoot = new BinaryTreeNode<type>(inorderListPivotData);
    if (!subRoot) {
        return false;
    }

    // 构造左子树
    bool res = _createSubTreeByPreorderAndInOrder(preorderList + 1,
                                                  inorderList,
                                                  inorderListPivot,
                                                  subRoot->lChild);

    if (!res) {
        return false;
    }

    res = _createSubTreeByPreorderAndInOrder(preorderList + inorderListPivot + 1,
                                             inorderList + inorderListPivot + 1,
                                             length - inorderListPivot - 1,
                                             subRoot->rChild);

    return res;
}

// 重载== 号
template<typename type>
bool operator==(const BinaryTree<type>& binary_tree_1, const BinaryTree<type>& binary_tree_2) {
    return BinaryTree<type>::equal(binary_tree_1.Root(), binary_tree_2.Root());
}

// 重载 << 输出运算符
template<typename type>
std::ostream& operator<<(std::ostream& out, BinaryTree<type>& binary_tree) {
    binary_tree.print();
    return out;
}


#endif